Mengikut sejarah, masyarakat Tidung wujud ini kawasan ini sejak zaman dahulu lagi. Mereka adalah etnik Muslim dan menggunakan bahasa Melayu untuk berkomunikasi dengan entiti masyarakat lain di sekitarnya seperti masyarakat Sungai ( Beluran dan Labuk ), masyarakat Suluk ( Lahad Datu dan Tungku ), masyarakat Idahan ( Silam dan Madai ), masyarakat Bajau ( Semporna dan Omadil ), masyarakat Bulungan ( Tanjung Selor), masyarakat Banjar ( Banjarmasin ), masyarakat Kutai dan masyarakat Berau yang merupakan penghuni asal di daerah Borneo Timur. Dalam catatan sejarah, sekitar tahun 1800an, terdapat beberapa buah kerajaan Kesultanan Melayu Islam yang wujud di Kalimantan Timur seperti Kesultanan Bulungan ( Sultan Kaharuddin I ) di Tanjung Palas, Kerajaan Tidung Tengara ( Amiril Pengiran Tadjuddin ) di Tarakan, Kesultanan Kutai, Kesultanan Berau, Kesultanan Paser (Sultan Sulaiman Alamsyah) di Balik Papan dan Kesultanan Banjar ( Sultan Tamjidullah II ). Menurut pembahagian suku kaum dayak di Kalimantan, Indonesia, Suku Tidung adalah suku Dayak Murut atau dikenali sebagai "Lun Pagun" iaitu Lun=Orang dan Pagun=Pagan yang pada mulanya tiada agama atau Pagan cuma menyembah nenek moyang yang akhirnya menerima islam. Ini jelas dilihat yang mana hampir 80% bahasa tidung sama dengan bahasa murut.

Masyarakat Tidung dahulu kala tinggal di sepanjang sungai-sungai di pertengahan Borneo Timur hingga sejauh ke utara di Batu Tinagat berdekatan Tawau. ( Henry Roth : 1896 ). Bukti jelas kewujudan bangsa Tidung adalah yang terawal di kawasan daerah Tawau ialah nama tempat yang dinamakan menggunakan panggilan dalam bahasa Tidung seperti nama Tinagat yang bermaksud 'tebang' dan Membalua yang bermaksud 'hantu'. Batu Tinagat atau Batu Payung berasal daripada cerita masyarakat Tidung Tawau iaitu pada zaman dahulu kala ada seorang pemuda yang ternampak puteri-puteri kayangan yang turun ke bumi untuk mandi di kawasan batu berbentuk payung lalu menyembunyikan salah satu pakaian puteri tersebut sehingga puteri tersebut tidak dapat kembali ke kayangan. Pemuda dan puteri tersebut berkahwin dan apabila puteri tersebut menyedari pakaiannya yang disembunyikan, beliau membuat helah tidak boleh menari di suatu majlis keramaian sekiranya tidak memakai baju kayangan miliknya. Pemuda tersebut tanpa mengesyaki isterinya terus mengembalikan pakaian tersebut dan apabila isterinya memakai pakaian tersebut, puteri itu terapung-apung di atas batu payung itu. Pemuda itu menebang batu payung tersebut tetapi sia-sia kerana isteri atau puteri terus terbang ke langit dan tidak kembali lagi. Sebab itu kita tidak melihat lagi bentuk batu payung yang sebenar kerana telah ditebang. Cerita ini juga telah dijadikan salah satu lagu dan tarian klasik suku kaum tidung berirama zapin diberi nama Seludon Batu Tinagat. Kampung Membalua pula dulunya dianggap kawasan berhantu. Tawau sendiri dipercayai dinamakan menggunakan panggilan dalam bahasa tidung yang bermaksud "pancing" atau "nawau". Ini berlaku apabila seorang orang putih bertanyakan nama tempat dia berada kepada seorang orang tidung yang sedang memancing yang kemudian dijawab "nawau" oleh orang tidung itu kerana ti dak faham bahasa inggeris. Disangkanya orang putih tersebut bertanya apa yang dia sedang lakukan. Kemudian orang putih itu terus berjalan dan sampai di suatu tempat pula dia bertanya lagi nama tempat yang dia berada kepada seorang orang tidung yang ditemuinya dan sekali lagi disalah anggap yang disambut dengan jawapan "Murut Tai" yang bermaksud tahi orang Murut kerana tempat mereka berdiri itu penuh dengan tahi manusia yang dipercayai oleh orang tidung tersebut ia adalah tahi orang murut. Maka tempat itu dinamakan Merotai. Apas pula berasal dari perkataan "apos" atau "ampus" atau sesak nafas.

Tercatat dalam sejarah yang mengatakan pernah wujud sebuah kerajaan Melayu Islam Tidung di Tarakan pada kurun ke 16 yang juga dikenali sebagai Kerajaan Tengara. Di dalam fakta sejarah Borneo, kerajaan Tidung di Tarakan bermula pada tahun 1557 dan lokasinya di kawasan Pamusian DI wilayah Tarakan Timur. Pemerintahnya yang pertama ialah Amir Rasyid ( Dato Raja Laut (1557-1571). Dinyatakan juga dalam fakta sejarah Borneo bahawa Sultan Tarakan yang ke 10 iaitu Amir Pengiran Jamalul Kiram ( 1844-1867 ) yang tiada waris lelaki, telah mengahwinkan puterinya, Putri Intan Dura dengan anak Sultan Bulungan Sultan Kaharudin II ( 1875-1889 ), Datu Maulana. Dan berikutan dari peristiwa itu, Datu Maulana telah menjadi Sultan Tarakan pada tahun 1867. Dan seterusnya putera mereka, Datu Adil ( 1896-1916 )adalah pemerintah Kerajaan Tidung Tarakan yang terakhir. Selain itu, terdapat juga bukti kewujudan penempatan masyarakat Tidung tertua di kawasan Pulau Kalumpang dan di sekitar Kuala Sungai Kalumpang berdekatan Semporna. Penempatan ini dikatakan dimulakan oleh seorang bangsawan bernama Pengiran Anum sekitar tahun 1800an. Kini di sana, masih wujud tapak perkuburan dan makam lama serta keturunan generasi ke 7 dan 8 kepada Pengeran Anum yang menjadi bukti kewujudan pemerintahan Pengiran Anum ini suatu masa dulu.